typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    ListNode* newHead, *newTail;
    newHead = newTail = (ListNode*)malloc(sizeof(ListNode));
    ListNode* L1 = list1;
    ListNode* L2 = list2;
    if((L1 == NULL) && (L2 == NULL))
    {
        return NULL;
    }
    while((L1 != NULL) && (L2 != NULL))
    {
        if(L1->val < L2->val)
        {
            newTail->next = L1;
            newTail = newTail->next;
            L1 = L1->next;
        }
        else
        {
            newTail->next = L2;
            newTail = newTail->next;
            L2 = L2->next;
        }
    }
    while(L1)
    {  
        newTail->next = L1;
        newTail = newTail->next;        
        L1 = L1->next;
    }
    while(L2)
    {
        newTail->next = L2;
        newTail = newTail->next;            
        L2 = L2->next;
    }
    ListNode* ret = newHead->next;
    free(newHead);
    newHead = NULL;
    return ret;
}